/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// 反转链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode new_head, *p = head, *q;
        new_head.next = nullptr;
        while (p)
        {
            q = p->next;
            // 将p指针不断插入虚拟头节点0位置完成链表反转
            p->next=new_head.next;
            new_head.next=p;
            p=q;

        }
        return new_head.next;
    }
};